1. Field of the Invention
The present invention relates to a multiple coding method and apparatus and a multiple decoding method and apparatus for detecting and correcting (or checking) errors that have occurred in a transmission medium, such as an optical cable, disposed in an information transmission system, or a storage medium, such as a hard disk drive, disposed in an information processing system. It also relates to an information transmission system including such a multiple coding apparatus and such a multiple decoding apparatus. More particularly, the present invention relates to an improvement in a multiple coding and decoding arrangement, typified by a product coding and decoding arrangement or a concatenated coding and decoding arrangement, aimed for improving error detecting and correcting performances, which is employed to efficiently reduce a delay in the information transmission caused by the multiple coding and decoding technique, thus providing a high transmission rate.
2. Description of the Prior Art
Prior art techniques of performing coding a number of times are disclosed by H. Imai, xe2x80x9cCoding theoryxe2x80x9d, published in 1990 by the Institute of Electronics, Information and Communication Engineers, Japan, and Japanese patent application publication (TOKKAIHEI) No. 10-190486, for example. Referring now to FIG. 6, there is illustrated a block diagram showing the structure of a prior art information transmission system for performing coding and decoding a number of times and for transmitting a sequence of pieces of information. In the figure, reference numeral 29 denotes a concatenated coding apparatus, numeral 30 denotes a concatenated decoding apparatus, and numeral 3 denotes a transmission medium connected between the concatenated coding apparatus 29 and the concatenated decoding apparatus 30.
The concatenated coding apparatus 29 includes an information sequence input circuit 31 for receiving an input sequence of pieces of information, a Reed-Solomon outer encoder 32 for encoding the input information sequence, an interleaving memory 33 for sequentially storing a plurality of outer coded sequences from the Reed-Solomon outer encoder, an address generating circuit 34 for controlling writing and reading to and from the interleaving memory 33, an Reed-Solomon inner encoder 35 for further encoding an input sequence read out of the interleaving memory 33, and a concatenated coded sequence output circuit 36 for furnishing a sequence of inner coded data from the Reed-Solomon inner encoder as an output sequence of concatenated coded data to the transmission medium 3.
The concatenated decoding apparatus 30 includes a concatenated coded sequence input circuit 37 for receiving an input sequence of concatenated coded data, an Reed-Solomon inner decoder 38 for decoding the input concatenated coded sequence, a de-interleaving memory 39 for sequentially storing a plurality of sequences of inner decoded data from the Reed-Solomon inner decoder, an address generating circuit 40 for controlling writing and reading to and from the de-interleaving memory 39, an Reed-Solomon outer decoder 41 for further decoding a sequence of decoded data read out of the de-interleaving memory, and an information sequence output circuit 42 for furnishing a sequence of outer decoded data from the Reed-Solomon outer decoder as an output sequence of pieces of information.
In operation, when an information sequence is applied to the information sequence input circuit 31, the Reed-Solomon outer encoder 32 encodes the input information sequence and sequentially stores the outer coded sequence from the outer encoder in the interleaving memory 33. When a predetermined number of outer coded sequences are written into the interleaving memory 33, the address generating circuit 34 makes the interleaving memory 33 sequentially furnish those sequences in an order opposite to the order in which they have been written into the interleaving memory. The Reed-Solomon inner encoder 35 further encodes the plurality of data sequences read out of the interleaving memory and generates a plurality of inner coded sequences, and the concatenated coded sequence output circuit 36 then furnishes the plurality of inner coded sequences from the Reed-Solomon encoder as a plurality of concatenated coded sequences to the transmission medium 3.
When the concatenated coded sequence input circuit 37 receives an input concatenated coded sequence of by way of the transmission medium 3, the Reed-Solomon inner decoder 38 decodes the input concatenated coded sequence and then stores the decoded result in the de-interleaving memory 39 sequentially. When a predetermined number of sequences of inner decoded data are written into the de-interleaving memory, the address generating circuit 40 makes the de-interleaving memory 39 sequentially furnish those sequences in an order opposite to the order in which they have been written into the de-interleaving memory. The Reed-Solomon outer decoder 41 further decodes the plurality of data sequences read out of the de-interleaving memory and generates a plurality of sequence of outer decoded data, and the information sequence output circuit 42 then furnishes the plurality of sequence of outer decoded data as a plurality of sequences of output information sequentially.
In this way, the prior art information transmission system can sequentially supply a plurality of information sequences to the concatenated coding apparatus 29, and then transmit a plurality of concatenated coded sequences generated by the concatenated coding apparatus 29, by way of the transmission medium 3, to the concatenated decoding apparatus 30 which decodes the plurality of concatenated coded sequences, so that the receive side of the system can get the plurality of information sequences error-detected and error-corrected.
A problem with prior art information transmission systems constructed as above is that in the concatenated coding apparatus 29, for example, the interleaving memory 33 has to have enough storage amount to sequentially store a predetermined number of outer coded sequences generated by the Reed-Solomon outer encoder 32 because the plurality of outer coded sequences must be sequentially read out of the interleaving memory 33 in an order opposite to the order in which they have been written into the interleaving memory in order to make the coding directions of the two encoders 32 and 35 differ from each other, thereby providing high error-detecting and error-correcting performances, and it is therefore impossible to read the next set of outer coded sequences until the writing of the previous set of outer coded sequences to the interleaving memory 33 is completed, thus causing a very long time delay in the coding process.
Referring next to FIG. 7, there is illustrated a format diagram for explaining the writing and reading operations of the interleaving memory 33 of the prior art information transmission system of FIG. 6. FIG. 7 shows an example in which the plurality of outer coded sequences from the Reed-Solomon outer encoder are written into the interleaving memory 33 such that they are running along columns from the leftmost column to the rightmost column, and a plurality of rows are sequentially read out of the interleaving memory, starting from the uppermost row, after the last outer coded sequence is written into the rightmost column. In the case of the use of such the interleaving memory 33, the reading process of reading the plurality of coded sequences running along rows cannot be performed until the writing process of writing the plurality of outer coded sequences into the memory locations from the leftmost column to the rightmost column is completed, thus causing a time delay. FIG. 8 shows an example in which the plurality of outer coded sequences are written into the interleaving memory 33 such that each of them is split across some columns.
Consequently, the total amount of memory required for interleaving processes and the total time delay caused by the interleaving processes increase with increase in the number of encoders disposed in the concatenated coding apparatus 29. Since the information transmission rate cannot exceed the maximum one limited by the total time delay, it is difficult to improve the transmission rate while ensuring the reliability of information transmitted. The concatenated decoding apparatus 30 has the same problem too.
The present invention is proposed to solve the above problem. It is therefore an object of the present invention to provide a multiple coding method and apparatus for performing coding having different coding directions a number of times with a shorter time delay than do prior art information transmission systems, thus providing a higher transmission rate than do prior art information transmission systems while ensuring the reliability of information transmitted, a multiple decoding method and apparatus for performing decoding having different decoding directions a number of times with a shorter time delay than do prior art information transmission systems, thus providing a higher transmission rate than do prior art information transmission systems while ensuring the reliability of information received, and an information transmission system including such a multiple coding apparatus and such a multiple decoding apparatus.
In accordance-with one aspect of the present invention, there is provided a multiple coding method comprising the steps of: encoding a plurality of input sequences in parallel so as to generate a plurality of output coded sequences in parallel while adding an error-correcting bit sequence to each of the plurality of input sequences; interleaving the plurality of output coded sequences applied thereto in parallel by permuting the plurality of output coded sequences on a bit-by-bit or symbol-by-symbol basis so as to generate a plurality of interleaved sequences in parallel; and encoding the plurality of interleaved sequences in parallel so as to generate a plurality of output coded sequences in parallel while adding an error-correcting bit sequence to each of the plurality of interleaved sequences.
Preferably, the plurality of input sequences to be encoded in the first encoding step are equal in number to those to be encoded in the second encoding step, and the plurality of interleaved sequences generated in the interleaving step are equal in number to the plurality of output coded sequences generated in the first encoding step.
In accordance with a preferred embodiment of the present invention, the interleaving step includes the steps of counting a number of bits or symbols sequentially applied thereto and included in one input sequence generated in the first encoding step, and changing a permutation of the plurality of parallel bits or symbols every time a count value obtained in the counting step increments by one.
In accordance with another aspect of the present invention, there is provided a multiple decoding method comprising the steps of: decoding a plurality of input sequences in parallel based on an error-correcting bit sequence included in each of the plurality of input sequences so as to generate a plurality of output decoded sequences in parallel; de-interleaving the plurality of output decoded sequences applied thereto in parallel by permuting the plurality of output decoded sequences on a bit-by-bit or symbol-by-symbol basis so as to generate a plurality of de-interleaved decoded sequences in parallel such that the plurality of de-interleaved decoded sequences are a same order as a corresponding plurality of input, sequences before they were interleaved through a corresponding interleaving process; and decoding the plurality of de-interleaved decoded sequences in parallel based on an error-correcting bit sequence included in each of the plurality of de-interleaved decoded sequences so as to generate a plurality of output decoded sequences in parallel.
Preferably, the plurality of input sequences to be decoded in the first decoding step are equal in number to those to be decoded in the second decoding step, and the plurality of de-interleaved decoded sequences generated in the de-interleaving step are equal in number to the plurality of output decoded sequences generated in the first decoding step.
In accordance with a preferred embodiment of the present invention, the de-interleaving step includes the steps of counting a number of bits or symbols sequentially applied thereto and included in one output decoded sequence generated in the first decoding step, and changing a permutation of the plurality of parallel bits or symbols every time a count value obtained in the counting step increments by one.
In accordance with a further aspect of the present invention, there is provided a multiple coding apparatus comprising: a first encoder for encoding a plurality of input sequences in parallel so as to generate a plurality of output coded sequences in parallel while adding an error-correcting bit sequence to each of the plurality of input sequences; an interleaving circuit for interleaving a plurality of input sequences that are the plurality of output coded sequences applied thereto in parallel from the first encoder by permuting the plurality of input sequences on a bit-by-bit or symbol-by-symbol basis so as to generate a plurality of interleaved coded sequences in parallel; and a second encoder for encoding the plurality of interleaved coded sequences applied thereto in parallel from the interleaving circuit so as to generate a plurality of output coded sequences in parallel while adding an error-correcting bit sequence to each of the plurality of interleaved coded sequences.
Preferably, the plurality of input sequences to be encoded by the first encoder are equal in number to those to be encoded by the second encoder, and the plurality of interleaved coded sequences generated by the interleaving circuit are equal in number to the plurality of output coded sequences generated by the first encoder.
In accordance with a preferred embodiment of the present invention, the interleaving circuit includes a counter for counting a number of bits or symbols sequentially applied thereto and included in one input sequence from the first encoder, and a plurality of selectors each of which selects a different input sequence from the plurality of input sequences on a bit-by-bit or symbol-by-symbol basis according to a count value of the counter, and furnishes the selected input sequence as one interleaved coded sequence on a bit-by-bit or symbol-by-symbol basis, a number of the plurality of selectors being equal to a number of the plurality of input sequences. Each of the plurality of selectors can select the same input sequence every time it performs the selection a predetermined number of times corresponding to the number of the plurality of input sequences.
In accordance with another preferred embodiment of the present invention, each of the first and second encoders adds the error-correcting bit sequence to each of the plurality of input sequences applied thereto using a Reed-Solomon coding method.
In accordance with another preferred embodiment of the present invention, the multiple coding apparatus further comprises a second interleaving circuit for interleaving a plurality of input sequences applied thereto in parallel by permuting the plurality of input sequences on a bit-by-bit or symbol-by-symbol basis so as to generate and furnish a plurality of interleaved sequences in parallel to the first encoder.
In accordance with another aspect of the present invention, there is provided a multiple decoding apparatus comprising: a first decoder for decoding a plurality of input sequences in parallel based on an error-correcting bit sequence included in each of the plurality of input sequences so as to generate a plurality of output decoded sequences in parallel; a de-interleaving circuit for de-interleaving a plurality of input sequences that are the plurality of output decoded sequences applied thereto in parallel from the first decoder by permuting the plurality of output decoded sequences on a bit-by-bit or symbol-by-symbol basis so as to generate a plurality of de-interleaved decoded sequences in parallel such that the plurality of de-interleaved decoded sequences are a same order as a corresponding plurality of input sequences before they were interleaved through a corresponding interleaving method; and a second decoder for decoding the plurality of de-interleaved decoded sequences applied thereto in parallel from the de-interleaving circuit based on an error-correcting bit sequence included in each of the plurality of de-interleaved decoded sequences so as to generate a plurality of output decoded sequences in parallel.
Preferably, the plurality of input sequences to be decoded by the first decoder are equal in number to those to be decoded by the second decoder, and the plurality of de-interleaved decoded sequences generated by the de-interleaving circuit are equal in number to the plurality of output decoded sequences generated by the first decoder.
In accordance with another preferred embodiment of the present invention, the de-interleaving circuit includes a counter for counting a number of bits or symbols sequentially applied thereto and included in one input sequence from the first decoder, and a plurality of selectors each of which selects a different input sequence from the plurality of input sequences on a bit-by-bit or symbol-by-symbol basis according to a count value of the counter, and furnishes the selected input sequence as one de-interleaved decoded sequence on a bit-by-bit or symbol-by-symbol basis, a number of the plurality of selectors being equal to a number of the plurality of input sequences. Each of the plurality of selectors can select the same input sequence every time it performs the selection a predetermined number of times corresponding to the number of the plurality of input sequences.
In accordance with another preferred embodiment of the present invention, each of the first and second decoders decodes the plurality of input sequences applied thereto in parallel using a Reed-Solomon coding method.
In accordance with another preferred embodiment of the present invention, the multiple decoding apparatus further comprises an interleaving circuit for interleaving the plurality of output decoded sequences applied thereto in parallel from the second decoder by permuting the plurality of output decoded sequences on a bit-by-bit or symbol-by-symbol basis so as to generate a plurality of interleaved decoded sequences in parallel, a third decoder for performing a same decoding process as performed by the first decoder on the plurality of interleaved decoded sequences applied thereto in parallel from the interleaving circuit so as to generate a plurality of output decoded sequences in parallel, a second de-interleaving circuit for performing a same de-interleaving process as performed by the first de-interleaving circuit on the plurality of output decoded sequences applied thereto in parallel from the third decoder so as to generate a plurality of de-interleaved decoded sequences in parallel, and a fourth decoder for performing a same decoding process as performed by the second decoder on the plurality of de-interleaved decoded sequences applied thereto in parallel from the second de-interleaving circuit so as to generate a plurality of output decoded sequences in parallel. The plurality of error-correcting bit sequences used by the first decoder can be transferred to the third decoder in order for the third decoder use them when decoding the plurality of interleaved decoded sequences from the interleaving circuit, and the plurality of error-correcting bit sequences used by the second decoder can be transferred to the fourth decoder in order for the fourth decoder use them when decoding the plurality of de-interleaved decoded sequences from the second de-interleaving circuit.
In accordance with another preferred embodiment of the present invention, the multiple decoding apparatus further comprises an error number estimating circuit for calculating a number of all error bits or symbols corrected by the first and second decoder and assuming the number as a number of errors that have occurred in a transmission medium via which input sequences are transmitted to the multiple decoding apparatus.
In accordance with a further aspect of the present invention, there is provided an information transmission system multiple coding apparatus comprising: a multiple coding apparatus including a first encoder for encoding a plurality of input sequences in parallel so as to generate a plurality of output coded sequences in parallel while adding an error-correcting bit sequence to each of the plurality of input sequences, an interleaving circuit for interleaving a plurality of input sequences that are the plurality of output coded sequences applied thereto in parallel from the first encoder by permuting the plurality of input sequences on a bit-by-bit or symbol-by-symbol basis so as to generate a plurality of interleaved coded sequences in parallel, a second encoder for encoding the plurality of interleaved coded sequences applied thereto in parallel from the interleaving circuit so as to generate a plurality of output coded sequences in parallel while adding an error-correcting bit sequence to each of the plurality of interleaved coded sequences, and an output circuit for sending out the plurality of output coded sequences from the second encoder, as a plurality of concatenated coded sequences, on a transmission medium; and a multiple decoding apparatus including an input circuit for receiving the plurality of concatenated coded sequences from the transmission medium and furnishing the plurality of concatenated coded sequences as a plurality of input sequences, a first decoder for decoding the plurality of input sequences in parallel based on an error-correcting bit sequence included in each of the plurality of input sequences so as to generate a plurality of output decoded sequences in parallel, a de-interleaving circuit for de-interleaving a plurality of input sequences that are the plurality of output decoded sequences applied thereto in parallel from the first decoder by permuting the plurality of output decoded sequences on a bit-by-bit or symbol-by-symbol basis so as to generate a plurality of de-interleaved decoded sequences in parallel such that the plurality of de-interleaved decoded sequences are a same as the corresponding plurality of input sequences before they were interleaved by the interleaving circuit of the multiple coding apparatus, and a second decoder for decoding the plurality of de-interleaved decoded sequences applied thereto in parallel from the de-interleaving circuit based on an error-correcting bit sequence included in each of the plurality of de-interleaved decoded sequences so as to generate a plurality of output decoded sequences in parallel.
Further objects and advantages of the present invention will be apparent from the following description of the preferred embodiments of the invention as illustrated in the accompanying drawings.